/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

/**
 * 快速排序（Quick Sort）是基于二分思想，对冒泡排序的一种改进。主要思想是确立一个基数，将小于基数的数字放到基数的左边，大于基数的数字放到基数的右边，然后再对这两部分数字进一步排序，从而实现对数组的排序。
 * <p>
 * 其优点是效率高，时间复杂度平均为O(nlog₂n)，顾名思义，快速排序是最快的排序算法，耗费的资源少，最佳情况下，空间复杂度为O(nlog₂n)，每一次都平分数组的情况，代码较为简单。
 * <p>
 * 其缺点是不稳定，初始序列有序或基本有序时，时间复杂度降为O(n²)。
 *
 * <a href="https://www.dotcpp.com/course/895">课程地址</a>
 *
 * @author lizhixing
 */
public class QuickSort {

  public static void main(String[] args) {
    int[] array = { 6, 17, 38, 59, 2, 10 };
    int low = 0, high = array.length - 1;
    print(array);
    quickRow(array, low, high);
    print(array);
  }

  //快排实现方法
  public static void quickRow(int[] array, int low, int high) {
    int i, j, pivot;
    //结束条件
    if (low >= high) {
      return;
    }
    i = low;
    j = high;
    //选择的节点，这里选择的数组的第一数作为节点
    pivot = array[low];
    while (i < j) {
      //从右往左找比节点小的数，循环结束要么找到了，要么i=j
      while (array[j] >= pivot && i < j) {
        j--;
      }
      //从左往右找比节点大的数，循环结束要么找到了，要么i=j
      while (array[i] <= pivot && i < j) {
        i++;
      }
      //如果i!=j说明都找到了，就交换这两个数
      if (i < j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
    //i==j一轮循环结束，交换节点的数和相遇点的数
    array[low] = array[i];
    array[i] = pivot;
    //数组“分两半”,再重复上面的操作
    quickRow(array, low, i - 1);
    quickRow(array, i + 1, high);
  }

  private static void print(int[] arr) {
    for (int i : arr) {
      System.out.print(i + "\t");
    }
    System.out.println();
  }

}
